// https://www.lintcode.com/problem/walls-and-gates/description

class Solution {
public:
    /**
     * @param rooms: m x n 2D grid
     * @return: nothing
     */
    
// 思路:
// • 问题简化:假设只有一个门
// – 即求每个房间到这个门的最短路 (多源点单终点) – 等价于这个门到所有房间的最短路(单源点多终点)
// • 因为是棋盘图，每个边的长度(权值)=1，所以最短路可以用BFS求出 – 这一题谁是盆地，谁是平原，谁是注水点
// – 最短路→BFS的第几层

    // void DFS(int x, int y, vector<vector<int>> &rooms, int val, bool start) 
    // {
    //     // 不要过分追求优雅，分情况讨论最好
    //     if (!(x >= 0 && x < rooms.size() && y >= 0 && y < rooms[0].size()) || rooms[x][y] == -1 || (rooms[x][y] <= val && !start))
    //     // 注意先判断元素是否存在，再判断元素内容！低级错误
    //     {
    //         return;
    //     }
    //     rooms[x][y] = min(rooms[x][y], val + 1);
    //     cout << x << " " << y << endl;
    //     cout << rooms[x][y] << endl;
    //     DFS(x + 1, y, rooms, rooms[x][y], false);
    //     DFS(x - 1, y, rooms, rooms[x][y], false);
    //     DFS(x, y + 1, rooms, rooms[x][y], false);
    //     DFS(x, y - 1, rooms, rooms[x][y], false);
    // }
    // void wallsAndGates(vector<vector<int>> &rooms) {
    //     int m = rooms.size();
    //     int n = rooms[0].size();
    //     for (int i = 0; i < m; ++i)
    //     {
    //         for (int j = 0; j < n; ++j)
    //         {
    //             // 中间也可以有门
    //             if (rooms[i][j] == 0)
    //             {
    //                 DFS(i, j, rooms, 0, true);
    //             }
    //         }
    //     }
        
    // }
    
    
    // 整理，思路要清晰
        // void DFS(int x, int y, vector<vector<int>> &rooms, int dis) 
    // {
    //     if (!(x >= 0 && x < rooms.size() && y >= 0 && y < rooms[0].size()) || rooms[x][y] == -1)
    //     // 注意先判断元素是否存在，再判断元素内容！低级错误
    //     {
    //         return;
    //     }
    //     if (rooms[x][y] > dis || dis == 0)
    //     {
    //         rooms[x][y] = dis;
    //         DFS(x + 1, y, rooms, dis + 1);
    //         DFS(x - 1, y, rooms, dis + 1);
    //         DFS(x, y + 1, rooms, dis + 1);
    //         DFS(x, y - 1, rooms, dis + 1);
    //     }
    // }
    
    // void wallsAndGates(vector<vector<int>> &rooms) {
    //     int m = rooms.size();
    //     int n = rooms[0].size();
    //     for (int i = 0; i < m; ++i)
    //     {
    //         for (int j = 0; j < n; ++j)
    //         {
    //             // 中间也可以有门
    //             if (rooms[i][j] == 0)
    //             {
    //                 DFS(i, j, rooms, 0);
    //             }
    //         }
    //     }
        
    // }
    
    
    // 思路:
// • 多个门，多源点多终点怎么办?
// – 多个源点同时注水，看谁流得快
// • 多源点同时注水，其实相当于增加了一个超级源点(dummy)，超级源点 连接每个普通源点一条边
// • 增加了超级源后，其实相当于从超级源的单源最短路
// 多源多终点→单源多终点 (增加超级源，最短路常用转化套路)>

    struct Node 
    {
        int x;
        int y;
    };
    
    void wallsAndGates(vector<vector<int>> &rooms) {
        int m = rooms.size();
        int n = rooms[0].size();
        queue<Node> q;
        int dx[4] = {-1, 0, 1, 0};
        int dy[4] = {0, 1, 0, -1};
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (rooms[i][j] == 0)
                {
                    Node n{i, j};
                    q.push(n);
                }
            }
        }
        while (!q.empty())
        {
            Node nd = q.front();
            q.pop();
            for (int i = 0; i < 4; ++i)
            {
                int x = nd.x + dx[i];
                int y = nd.y + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && rooms[x][y] != -1 && rooms[x][y] == INT_MAX)
                // BFS本身直接按路径远近来，不用判断rooms[x][y] > rooms[nd.x][nd.y]，不用重复对比
                {
                    rooms[x][y] = rooms[nd.x][nd.y] + 1;
                    q.push(Node{x, y});
                }
            }
        }
    }
    
    
    // • 细节问题:不能达到的地方填INF怎么处理?
// – 其实题目的输入+ BFS 已经帮忙处理了，BFS搜不到的地方就会保留题目 的原始输入INF


};